#include "fs/buf.h"
#include "fs/bitmap.h"
#include "fs/inode.h"
#include "fs/fs.h"
#include "mem/vmem.h"
#include "proc/cpu.h"
#include "lib/print.h"
#include "lib/str.h"

extern super_block_t sb;

// 内存中的inode资源 + 保护它的锁
#define N_INODE 32
static inode_t icache[N_INODE];
static spinlock_t lk_icache;

// icache初始化
void inode_init()
{
    spinlock_init(&lk_icache, "icache");
    for(int i=0;i<N_INODE;i++)
    {
        icache[i].inode_num = INODE_NUM_UNUSED;
        icache[i].ref = 0;
        icache[i].valid = false;
        //test
        icache[i].inode_num = (uint16)-1;  // 标记为无效
        //test
        sleeplock_init(&icache[i].slk, "inode");
    }

}

/*---------------------- 与inode本身相关 -------------------*/

// 使用磁盘里的inode更新内存里的inode (write = false)
// 或 使用内存里的inode更新磁盘里的inode (write = true)
// 调用者需要设置inode_num并持有睡眠锁
void inode_rw(inode_t* ip, bool write)
{
    assert(ip->inode_num != INODE_NUM_UNUSED, "inode_rw: invalid inode_num");
    assert(sleeplock_holding(&ip->slk), "inode_rw: lock");

    // 确定该inode在磁盘上的位置
    // inode_num对应的block和inode在该block中的偏移
    uint32 block_num = sb.inode_start + ip->inode_num / INODE_PER_BLOCK;
    uint32 index_in_block = ip->inode_num % INODE_PER_BLOCK;

    buf_t* b = buf_read(block_num);
    inode_disk_t* dinode = ((inode_disk_t*)b->data) + index_in_block;

    if (!write) {
        // 从磁盘读入到内存
        ip->type  = dinode->type;
        ip->major = dinode->major;
        ip->minor = dinode->minor;
        ip->nlink = dinode->nlink;
        ip->size  = dinode->size;
        memmove(ip->addrs, dinode->addrs, sizeof(ip->addrs));
    } else {
        // 将内存中的inode写回磁盘
        dinode->type  = ip->type;
        dinode->major = ip->major;
        dinode->minor = ip->minor;
        dinode->nlink = ip->nlink;
        dinode->size  = ip->size;
        memmove(dinode->addrs, ip->addrs, sizeof(ip->addrs));

        // 强制将修改过的块写回磁盘
        buf_write(b);
    }

    // 释放buf
    buf_release(b);
}

// 在icache里查询inode
// 如果没有查询到则申请一个空闲inode
// 如果icache没有空闲inode则报错
// 注意: 获得的inode没有上锁
inode_t* inode_alloc(uint16 inode_num)
{    // 保证互斥访问icache
    spinlock_acquire(&lk_icache);
    // 1. 检查icache中是否已有该inode
    for (int i = 0; i < N_INODE; i++) {
        inode_t* ip = &icache[i];
        if (ip->ref > 0 && ip->inode_num == inode_num) {
            ip->ref++;
            spinlock_release(&lk_icache);
            return ip;
        }
    }

    // 2. 未找到则需要分配空闲inode结构(ref=0的)
    for (int i = 0; i < N_INODE; i++) {
        inode_t* ip = &icache[i];
        if (ip->ref == 0) {
            ip->ref = 1;
            ip->valid = false;
            ip->inode_num = inode_num;
            spinlock_release(&lk_icache);
            return ip;
        }
    }

    // 3. 没有空闲的inode槽位
    spinlock_release(&lk_icache);
    panic("inode_alloc: no free inode");
    return NULL; // 不会执行到这里
}

// 在磁盘里申请一个inode (操作bitmap, 返回inode_num)
// 向icache申请一个inode数据结构
// 填写内存里的inode并以此更新磁盘里的inode
// 注意: 获得的inode没有上锁
inode_t* inode_create(uint16 type, uint16 major, uint16 minor)
{
    
    // 1. 分配一个新的inode号
    uint16 inode_num = bitmap_alloc_inode();
    // 2. 在icache中分配该inode的内存结构
    inode_t* ip = inode_alloc(inode_num);
    if (ip == NULL) {
        panic("inode_create: inode_alloc failed");
    }

    // 3. 对inode上锁，以安全地修改其元数据
    inode_lock(ip);
    // 4. 初始化inode的元数据
    ip->type = type;
    ip->major = major;
    ip->minor = minor;
    ip->nlink = 1;    // 对新创建的inode，通常先设置为1个链接数
    ip->size = 0;
    for (int i = 0; i < N_ADDRS; i++) {
        ip->addrs[i] = 0;
    }

    // 设置valid为true，表示内存中的inode数据已经与磁盘同步过
    ip->valid = true;

    // 5. 将inode信息写回磁盘，使之在磁盘上也生效
    inode_rw(ip, true);

    // 6. 解锁inode
    inode_unlock(ip);

    // 返回给调用者使用，此时inode并没有被释放，上层可以继续使用它
    return ip;

}

// 供inode_free调用
// 在磁盘上删除一个inode及其管理的文件 (修改inode bitmap + block bitmap)
// 调用者需要持有lk_icache, 但不应该持有slk(???????????)
static void inode_destroy(inode_t* ip)
{
    assert(!spinlock_holding(&lk_icache), "inode_destroy: lk");
    assert(sleeplock_holding(&ip->slk), "inode_destroy: slk");

    // 释放该 inode 管理的所有数据块
    inode_free_data(ip);

    // 清空 inode 的元数据，标记为未使用
    ip->type = FT_UNUSED;
    ip->major = 0;
    ip->minor = 0;
    ip->nlink = 0;
    ip->size = 0;
    for(int i = 0; i < N_ADDRS; i++) {
        ip->addrs[i] = 0;
    }

    // 将清空后的 inode 写回磁盘，确保磁盘和内存的一致性
    inode_rw(ip, true);
    // 释放该 inode 在 bitmap 中的标记，表示该 inode 号可重新分配
    
    bitmap_free_inode(ip->inode_num);
}

// 向icache里归还inode
// inode->ref--
// 调用者不应该持有slk
void inode_free(inode_t* ip)
{

    // 检查引用计数是否有效
    if(ip->ref == 0){
        panic("inode_free: trying to free inode with ref=0");
    }
    if(ip->ref == 1&& ip->nlink == 0 && ip->type != FT_UNUSED)
    {   
        inode_lock(ip);
        inode_destroy(ip);
        ip->type=FT_UNUSED;
        inode_rw(ip,true);
        ip->valid=0;
        inode_unlock(ip);
    }
    spinlock_acquire(&lk_icache);
    // 递减引用计数
    ip->ref--;
    spinlock_release(&lk_icache);
}

// ip->ref++ with lock
inode_t* inode_dup(inode_t* ip)
{
    spinlock_acquire(&lk_icache);
    ip->ref++;
    spinlock_release(&lk_icache);
    return ip;
}

// 给inode上锁
// 如果valid失效则从磁盘中读入
void inode_lock(inode_t* ip)
{
    if (ip == 0)
        panic("inode_lock:ip == 0");
    if (ip->ref < 1)
        panic("inode_lock:ip->ref < 1");
    sleeplock_acquire(&ip->slk);
    if (ip->valid == 0)
    {
        inode_rw(ip, false);
        ip->valid = 1;
        assert(ip->type==FT_UNUSED||ip->type==FT_DIR||ip->type==FT_FILE||ip->type==FT_DEVICE,"unvalid type");
    }

}

// 给inode解锁
void inode_unlock(inode_t* ip)
{
    assert(ip&&sleeplock_holding(&(ip->slk))&&ip->ref>=1,"inode_unlock: invalid inode or not holding lock");
    sleeplock_release(&ip->slk);
}

// 连招: 解锁 + 释放
void inode_unlock_free(inode_t* ip)
{
    inode_unlock(ip);
    inode_free(ip);
}

/*---------------------------- 与inode管理的data相关 --------------------------*/

// 辅助 inode_locate_block
// 递归查询或创建block
// static uint32 locate_block(uint32* entry, uint32 bn, uint32 size)
// {
//     if(*entry == 0)
//         *entry = bitmap_alloc_block();

//     if(size == 1)
//         return *entry;    

//     uint32* next_entry;
//     uint32 next_size = size / ENTRY_PER_BLOCK;
//     uint32 next_bn = bn % next_size;
//     uint32 ret = 0;

//     buf_t* buf = buf_read(*entry);
//     next_entry = (uint32*)(buf->data) + bn / next_size;
//     ret = locate_block(next_entry, next_bn, next_size);
//     buf_release(buf);

//     return ret;
// }

// 确定inode里第bn块data block的block_num
// 如果不存在第bn块data block则申请一个并返回它的block_num
// 由于inode->addrs的结构, 这个过程比较复杂, 需要单独处理
static uint32 inode_locate_block(inode_t* ip, uint32 bn)
{
    // 确保持有inode的锁
    assert(sleeplock_holding(&ip->slk), "inode_locate_block: not holding slk");

    uint32 result = 0;

    // 如果bn小于N_ADDRS_1，说明是直接块
    if (bn < N_ADDRS_1) {
        result = ip->addrs[bn];  // 直接块就是addrs数组中的元素
        if (result == 0) {
            // 如果该直接块尚未分配，分配新的块
            result = bitmap_alloc_block();
            assert(result != -1, "inode_locate_block: bitmap_alloc_block failed");
            ip->addrs[bn] = result;  // 更新inode的addrs
        }
    }
    // 如果bn在一级间接块的范围内
    else if (bn < N_ADDRS_1 + N_ADDRS_2 * ENTRY_PER_BLOCK) {
        // 计算bn所在的一级间接块索引
        int index1 = (bn - N_ADDRS_1) / ENTRY_PER_BLOCK + N_ADDRS_1;

        // 第一次寻址：获取一级间接块地址
        uint32 sub_block1 = ip->addrs[index1];
        if (sub_block1 == 0) {
            // 如果一级间接块未分配，分配一个新的块
            sub_block1 = bitmap_alloc_block();
            assert(sub_block1 != 0, "inode_locate_block: bitmap_alloc_block failed");
            ip->addrs[index1] = sub_block1;
        }

        // 第二次寻址：计算一级间接块中的索引
        int index2 = (bn - N_ADDRS_1) % ENTRY_PER_BLOCK;
        buf_t* sub_table1 = buf_read(sub_block1);  // 读取一级间接块
        result = *((uint32*)sub_table1->data + index2);  // 获取具体的块号
        if (result == 0) {
            // 如果该位置为空，分配新的块
            result = bitmap_alloc_block();
            assert(result != 0, "inode_locate_block: bitmap_alloc_block failed");
            *((uint32*)sub_table1->data + index2) = result;  // 更新一级间接块
        }
        buf_write(sub_table1);  // 写回一级间接块
        buf_release(sub_table1);  // 释放buf
    }
    // 如果bn在二级间接块的范围内
    else if (bn < N_ADDRS_1 + N_ADDRS_2 * ENTRY_PER_BLOCK + N_ADDRS_3 * ENTRY_PER_BLOCK * ENTRY_PER_BLOCK) {
        // 计算bn所在的二级间接块索引
        int index1 = (bn - N_ADDRS_1 - ENTRY_PER_BLOCK * N_ADDRS_2) / (ENTRY_PER_BLOCK * ENTRY_PER_BLOCK) + N_ADDRS_1 + N_ADDRS_2;

        // 第一次寻址：获取二级间接块地址
        uint32 sub_block1 = ip->addrs[index1];
        if (sub_block1 == 0) {
            // 如果二级间接块未分配，分配一个新的块
            sub_block1 = bitmap_alloc_block();
            assert(sub_block1 != 0, "inode_locate_block: bitmap_alloc_block failed");
            ip->addrs[index1] = sub_block1;
        }

        // 第二次寻址：计算二级间接块中的索引
        int index2 = (bn - N_ADDRS_1 - ENTRY_PER_BLOCK * N_ADDRS_2) / ENTRY_PER_BLOCK;
        uint32 sub_block2 = 0;
        buf_t* sub_table1 = buf_read(sub_block1);  // 读取二级间接块
        sub_block2 = *((uint32*)sub_table1->data + index2);  // 获取二级间接块的地址
        if (sub_block2 == 0) {
            // 如果该位置为空，分配新的块
            sub_block2 = bitmap_alloc_block();
            assert(sub_block2 != 0, "inode_locate_block: bitmap_alloc_block failed");
            *((uint32*)sub_table1->data + index2) = sub_block2;  // 更新二级间接块
        }
        buf_write(sub_table1);  // 写回二级间接块
        buf_release(sub_table1);  // 释放buf

        // 第三次寻址：计算三级间接块中的索引
        int index3 = (bn - N_ADDRS_1 - ENTRY_PER_BLOCK * N_ADDRS_2) % ENTRY_PER_BLOCK;
        buf_t* sub_table2 = buf_read(sub_block2);  // 读取三级间接块
        result = *((uint32*)sub_table2->data + index3);  // 获取最终数据块地址
        if (result == 0) {
            // 如果该位置为空，分配新的块
            result = bitmap_alloc_block();
            assert(result != 0, "inode_locate_block: bitmap_alloc_block failed");
            *((uint32*)sub_table2->data + index3) = result;  // 更新三级间接块
        }
        buf_write(sub_table2);  // 写回三级间接块
        buf_release(sub_table2);  // 释放buf
    } else {
        panic("inode_locate_block: invalid block number");
    }

    // // 更新inode的size字段，确保它包含新分配的块
    // if (ip->size < (bn + 1) * BLOCK_SIZE) {
    //     ip->size = (bn + 1) * BLOCK_SIZE;
    //     inode_rw(ip, true);  // 更新inode
    // }

    return result;

}

// 读取 inode 管理的 data block
// 调用者需要持有 inode 锁
// 成功返回读出的字节数, 失败返回0
uint32 inode_read_data(inode_t* ip, uint32 offset, uint32 len, void* dst, bool user)
{
    assert(sleeplock_holding(&ip->slk), "inode_read_data: not holding slk");

    if(offset > ip->size || offset + len < offset )
        panic("inode_read_data: offset");
    //read的字节数不能超过size大小，但是write其实是可以把size写大的，只要不超过INODE_MAXSIZE
    if(offset + len > ip->size)
        len = ip->size - offset;
    //根据offset找到起始的块的逻辑号和结束的块的逻辑号
    uint32 bn = offset / BLOCK_SIZE;
    uint32 end_bn = (offset + len - 1) / BLOCK_SIZE;

    uint32 off = offset % BLOCK_SIZE;
    //读取的总字节数
    uint32 n = 0;
    uint32 block_num;
    buf_t* buf;
    proc_t* p = myproc();
    pgtbl_t user_pgtbl=p->pgtbl;

    for(; bn <= end_bn; bn++)
    {
        //根据bn逻辑号找到对应的物理块号
        block_num = inode_locate_block(ip, bn);
        //根据物理块号读出真正的block（以buf为介质）
        buf = buf_read(block_num);
        uint32 copy_len = MIN(len - n, BLOCK_SIZE - off);
        if(user)
            uvm_copyout(user_pgtbl,(uint64)(dst + n), (uint64)(buf->data + off), copy_len);
        else
            memmove(dst + n, buf->data + off, copy_len);
        buf_release(buf);
        n += copy_len;
        off = 0;
    }
    
    return n;
}

// 写入 inode 管理的 data block (可能导致管理的 block 增加)
// 调用者需要持有 inode 锁
// 成功返回写入的字节数, 失败返回0
uint32 inode_write_data(inode_t* ip, uint32 offset, uint32 len, void* src, bool user)
{
    assert(sleeplock_holding(&(ip->slk)),"inode_write_data: not holding slk");

    if(offset + len < offset)
        panic("inode_write_data: offset");
    if(offset + len > INODE_MAXSIZE)
        panic("inode_write_data: too large");
    uint32 n = 0;
    uint32 block_num;
    buf_t* buf;
    proc_t* p = myproc();

    pgtbl_t user_pgtbl=p->pgtbl;
    uint32 bn = offset / BLOCK_SIZE;
    uint32 end_bn = (offset + len - 1) / BLOCK_SIZE;
    uint32 off = offset % BLOCK_SIZE;

    for(; bn <= end_bn; bn++)
    {   
        //根据bn逻辑号找到对应的物理块号
        block_num = inode_locate_block(ip, bn);
        //根据物理块号读出真正的block（以buf为介质）
        buf = buf_read(block_num);
        uint32 copy_len = MIN(len - n, BLOCK_SIZE - off);
        if(user){
            uvm_copyin(user_pgtbl,(uint64)(buf->data + off), (uint64)(src + n), copy_len);
        }
        else{
            memmove(buf->data + off, src + n, copy_len);
        }
        buf_write(buf);
        buf_release(buf);
        n += copy_len;
        off = 0;
    }
    if(offset + n > ip->size)
    {
        ip->size = offset + n;
        inode_rw(ip, true);
    }

    return n;
}

// 辅助 inode_free_data 做递归释放
static void data_free(uint32 block_num, uint32 level)
{  
    assert(block_num != 0, "data_free: block_num = 0");

    // block_num 是 data block
    if(level == 0) goto ret;

    // block_num 是 metadata block
    buf_t* buf = buf_read(block_num);
    for(uint32* addr = (uint32*)buf->data; addr < (uint32*)(buf->data + BLOCK_SIZE); addr++) 
    {
        if(*addr == 0) break;
        data_free(*addr, level - 1);
    }
    buf_release(buf);

ret:
    bitmap_free_block(block_num);
    return;
}

// 释放inode管理的 data block
// ip->addrs被清空 ip->size置0
// 调用者需要持有slk
void inode_free_data(inode_t* ip)
{
    assert(sleeplock_holding(&ip->slk), "inode_free_data: lk");
    // 释放一级地址块
    for (int i = 0; i < N_ADDRS_1; i++) {
        if (ip->addrs[i] != 0) {
            data_free(ip->addrs[i], 0);  // 一级地址块直接是数据块
            ip->addrs[i] = 0;  // 清空地址
        }
    }

    // 释放二级地址块
    for (int i = N_ADDRS_1; i < N_ADDRS_1 + N_ADDRS_2; i++) {
        if (ip->addrs[i] != 0) {
            data_free(ip->addrs[i], 1);  // 二级地址块指向一级块
            ip->addrs[i] = 0;  // 清空地址
        }
    }

    // 释放三级地址块
    for (int i = N_ADDRS_1 + N_ADDRS_2; i < N_ADDRS; i++) {
        if (ip->addrs[i] != 0) {
            data_free(ip->addrs[i], 2);  // 三级地址块指向二级块
            ip->addrs[i] = 0;  // 清空地址
        }
    }

    // 将 inode 的 size 设置为 0，表示没有数据
    ip->size = 0;
}

static char* inode_types[] = {
    "INODE_UNUSED",
    "INODE_DIR",
    "INODE_FILE",
    "INODE_DEVICE",
};

// 输出inode信息
// for dubug
void inode_print(inode_t* ip)
{
    assert(sleeplock_holding(&ip->slk), "inode_print: lk");

    printf("\ninode information:\n");
    printf("num = %d, ref = %d, valid = %d\n", ip->inode_num, ip->ref, ip->valid);
    printf("type = %s, major = %d, minor = %d, nlink = %d\n", inode_types[ip->type], ip->major, ip->minor, ip->nlink);
    printf("size = %d, addrs =", ip->size);
    for(int i = 0; i < N_ADDRS; i++)
        printf(" %d", ip->addrs[i]);
    printf("\n");
}